# !/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
===========================
@Time : 2022/11/11 0011 19:31
@Author : 测试开发工程师
@File : 1. 时间复杂度 和 空间复杂度.py
@Software: PyCharm
============================
"""

"""
算法基础 ： 代码量少 + 运行速度快（内核）
    
    算法概念：
        算法（Algorithm）: 一个计算过程，解决问题的方法。
        程序 = 数据结构（静态：变量，列表，字典） +  算法
        输入 -> 算法 -> 输出
    
    时间复杂度： 
        n 表示 规模（问题复杂度）
        O(n)
        O(n^2)
        O(log2^n)  2^6 = 64 -> log2^64 = 6
        时间复杂度是用来估计算法运行时间的一个式子（单位）
        一般来说,时间复杂度高的算法比复杂度低的算法慢
        常见的时间复杂度（按效率排序）：
            O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^2logn) < O(n^3)
        复杂问题的时间复杂度：
            O(n!) O(2^n) O(n^n) ......
    
    空间复杂度
        空间复杂度：用来评估算法内存占用大小的式子
        空间复杂度的表示方式与时间复杂度完全一样
            算法使用了几个变量： O(1)
            算法使用了长度为 n 的一维列表：O(n)
            算法使用了 n 行 n 列的二维列表：O(mn)
        空间换时间：分布式运算
        
    递归
    递归的两个特点：
        调用自身
        结束条件
"""


# 汉诺塔
def hanni(n, a, b, c):
    if n > 0:
        # 第一步：把 n-1 个圆盘从 A 经过 C 移动到 B
        hanni(n - 1, a, c, b)
        print(f"moving from {a} to {c}")
        # 第三步：把 n-1 个 小圆盘从 B 经过 A 移动到 C
        hanni(n - 1, b, a, c)


# hanni(64) = 18446744073709551615，假如每秒搬一个盘子，总共需要 5800 亿年！
hanni(3, 'A', 'B', 'C')



